Eine formale Grammatik G ist ein 4-Tupel, bestehend aus einer endlichen Menge N von Nichtterminalsymbolen (im Folgenden kurz Nichtterminale, häufig aber auch Variablen genannt), einer endlichen Menge Σ von Terminalsymbolen (im Folgenden kurz Terminale genannt) (wobei das Alphabet Σ und die Nichtterminale N disjunkt sind), einer endlichen Menge P von Produktionsregeln (im Folgenden kurz Regeln, häufig auch Produktionen, genannt) und einem Startsymbol S, welches zu den Nichtterminalen gehört:

, ,

Nichtterminale werden gewöhnlich durch Großbuchstaben, Terminale durch Kleinbuchstaben repräsentiert.

Eine Regel besteht aus einer linken und einer rechten Seite, die jeweils ein Wort bestehend aus Terminalen und Nichtterminalen sind. Die linke Seite muss mindestens ein Nichtterminal beinhalten und die rechte Seite kann dabei in dem Gegensatz zur linken Seite auch das leere Wort (im Folgenden mit symbolisiert) sein, also das Wort der Länge Null:

Eine Regel kann auf ein Wort, bestehend aus Terminalen und Nichtterminalen, angewendet werden, wobei ein beliebiges Vorkommen der linken Seite der Regel in dem Wort durch die rechten Seite der Regel ersetzt wird. Für solche Produktionen hat sich folgende Schreibweise eingebürgert:

Eine Folge von Anwendungen solcher Regeln bezeichnet man als Ableitung, siehe dort.

Eine Grammatik G erzeugt eine formale Sprache , die aus allen Wörtern besteht, die ca. aus Terminalen bestehen und vom Startsymbol abgeleitet werden können:

symbolisiert hierbei die so genannte Transitionsrelation, siehe dort.

Wir betrachten die Grammatik mit den Terminalen {a,b}, den Nichtterminalen {S,A,B} mit dem Startsymbol S und den Regeln

Sie definiert die Sprache aller Wörter der Form , d.h. n Kopien von a gefolgt von n Kopien von b.

Hierbei ist zu beachten, dass dies nicht die einzige Grammatik ist, die diese Sprache erzeugt. Eine weitere Grammatik zur Erzeugung von ist die mit diesen Regeln

oder auch ca. schlicht:

Man sieht also, dass es zur Erzeugung einer Sprache mehrere (genaugenommen: beliebig viele) Grammatiken gibt.

Man klassifiziert verschiedene Typen von Grammatiken in der so genannten Chomsky-Hierarchie. Die obige wäre z.B Typ2